/*
** 3481.c
** 
** Made by (seakage2h)
** Login   <seakage2h@seakage2h-ubuntu>
** 
** Started on  Mon Sep 22 21:50:48 2008 seakage2h
** Last update Sun May 12 01:17:25 2002 Speed Blue
*/

/* #include "3481.h" */

/*
 * EXPERIENCE: list is neccesary.... TLE
 */

#include <stdio.h>
#include <stdlib.h>

int main()
{
     int* priority = (int*)calloc(10000001, sizeof(int));
     int head, tail;
     int opcode;
     int c, p;			/* customer number and its priority */
     
     head = tail = 0;

     while(scanf("%d", &opcode))
	  if (opcode == 1) break;
	  else if (!opcode) return 0;
	  else printf("0\n");

     scanf("%d%d", &c, &p);
     head = tail = p;
     priority[p] = c;

     while(scanf("%d", &opcode))
	  switch(opcode){
	  case 2:
	       if (head == tail){
		    if (priority[tail]){
			 printf("%d\n", priority[tail]);
			 priority[tail] = 0;
		    }
		    else printf("0\n");
		    break;
	       }
	       printf("%d\n", priority[tail]);
	       priority[tail] = 0;
	       while(!priority[tail]) tail--;
	       break;
	  case 3:
	       if (head == tail){
		    if (priority[head]){
			 printf("%d\n", priority[head]);
			 priority[head] = 0;
		    }
		    else printf("0\n");
		    break;
	       }
	       printf("%d\n", priority[head]);
	       priority[head] = 0;
	       while(!priority[head]) head++;
	       break;
	  case 1:
	       scanf("%d%d", &c, &p);
	       priority[p] = c;
	       if (p < head) head = p;
	       if (p > tail) tail = p;
	       break;
	  case 0:
	       return 0;
	       break;
	  }
     return 0;
}

